package newcoder_exp.unknown;

import java.util.*;

import org.junit.Test;

import linked.ListNode;
import utils.ArrayGenerator;

public class U3 {

    @Test
    public void test(){
        int[] vals = ArrayGenerator.getArray(20, 10);
        vals = new int[]{0, 8, 11};
        System.out.println(Arrays.toString(vals));
        ListNode head = ListNode.newListNodeFromArray(vals);

        Arrays.sort(vals);
        System.out.println(mergeSort(head));
    }
    
    //链表归并排序
    public ListNode mergeSort(ListNode head) {
        if (head == null || head.next == null) return head;
        return divide(head, null);
    }

    //对从head 到 end 这一段链表进行拆分
    public ListNode divide(ListNode head, ListNode end) {
        if (head == end || head.next == end) return head;
        ListNode mid = findMiddle(head, end), head2 = mid.next;
        mid.next = null;
        ListNode left = divide(head, mid.next), 
        right = divide(head2, end);
        ListNode res = merge(left, right);
        return res;
    }

    @Test
    public void test4(){
        ListNode head = ListNode.newListNodeFromArray(new int[]{10,4,2});
        ListNode res = divide(head, null);
        System.out.println(res);
    //     ListNode head2 = head.next.next;
    //     head.next.next = null;
    //    System.out.println( merge(head, head2));;
    }

    @Test
    public void test3() {
        int[] vals = ArrayGenerator.getArray(20, 10);
        vals = new int[]{0, 8, 11, 13, 5, 5, 7, 9, 12, 17, 6};
        // vals = new int[]{0, 8, 11, 13, 5, 5, 7, 9, 12, 17, 6, 4};
        vals = new int[]{10, 8, 11};
        System.out.println(Arrays.toString(vals));
        ListNode head = ListNode.newListNodeFromArray(vals);
        List<ListNode> list = ListNode.newListNodeFromArray(vals, true);
        ListNode res = divide(list.get(0), null);
        System.out.println(res);
    }

    public ListNode merge(ListNode left, ListNode right) {
        ListNode res = new ListNode(0), result = res;
        while (left != null && right != null) {
            if (left.val <= right.val) {
                res.next = left;
                left = left.next;
            } else {
                res.next = right;
                right = right.next;
            }
            res = res.next;
        }

        if (left == null) left = right;

        res.next = left;
        return result.next;
    }


    

    //奇数个节点，返回中间节点
    //偶数个节点，返回中间靠右节点
    public ListNode findMiddle(ListNode head, ListNode end) {
        /* ListNode slow = head.next;
        if (slow == end) return head;
        if (slow.next == end) return slow;
        ListNode fast = slow.next;

        for (; fast != end && fast.next != end;) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow.next; */
        if (head == end || head.next == end) return head == end ? head : head.next;
        ListNode fast = head, slow = head;
        while (fast != end && fast.next != end) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }


    @Test
    public void test2() {
        int[] vals = ArrayGenerator.getArray(20, 10);
        vals = new int[]{0, 8, 11, 13, 5, 5, 7, 9, 12, 17, 6};
        // vals = new int[]{0, 8, 11, 13, 5, 5, 7, 9, 12, 17, 6, 4};
        vals = new int[]{0, 8, 11};
        // vals = new int[]{0, 8, 11, 4};
        System.out.println(Arrays.toString(vals));
        ListNode head = ListNode.newListNodeFromArray(vals);
        List<ListNode> list = ListNode.newListNodeFromArray(vals, true);
        System.out.println(findMiddle(list.get(0), list.get(2)));
        System.out.println(findMiddle(list.get(0), null));
    }
}
